class Solution(object):
    def pourWater(self, heights, volume, k):
        """
        :type heights: List[int]
        :type volume: int
        :type k: int
        :rtype: List[int]
        """
        n = len(heights)

        def search(i, direction):
            left = float('inf')
            if i - 1 >= 0:
                left = min(left, heights[i - 1])
            right = float('inf')
            if i + 1 < n:
                right = min(right, heights[i + 1])
            if direction == 0:
                if heights[i] < right:
                    if heights[i] < left:
                        heights[i] += 1
                        return True
                    else:
                        if search(i - 1, 0):
                            return True
                        else:
                            heights[i] += 1
                            return True
                else:
                    if heights[i] < left:
                        return False
                    else:
                        return search(i - 1, 0)
            else:
                if heights[i] < left:
                    if heights[i] < right:
                        heights[i] += 1
                        return True
                    else:
                        if search(i + 1, 1):
                            return True
                        else:
                            heights[i] += 1
                            return True
                else:
                    if heights[i] < right:
                        return False
                    else:
                        return search(i + 1, 1)

        for v in range(volume):
            if search(k, 0):
                continue
            if search(k, 1):
                continue
            heights[k] += 1
        return heights


data = Solution()
heights = [2, 1, 1, 2, 1, 2, 2]
volume = 4
k = 3
print(data.pourWater(heights, volume, k))
heights = [1, 2, 3, 4]
volume = 2
k = 2
print(data.pourWater(heights, volume, k))
heights = [3, 1, 3]
volume = 5
k = 1
print(data.pourWater(heights, volume, k))
heights = [1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 3, 2, 1]
volume = 5
k = 5
print(data.pourWater(heights, volume, k))
